In graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges. It can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.
Contents |
There are two closely related variants of the Erdős–Rényi (ER) random graph model.
The behavior of random graphs are often studied in the case where n, the number of vertices, tends to infinity. Although p and M can be fixed in this case, they can also be functions depending on n. For example, the statement "almost every graph in is connected" means "as n tends to infinity, the probability that a graph on n vertices with edge probability is connected tends to 1".
The expected number of edges in G(n,p) is , and by the law of large numbers any graph in G(n,p) will almost surely have approximately this many edges (provided the expected number of edges tends to infinity). Therefore a rough heuristic is that if tends to infinity, then G(n,p) should behave similarly to G(n,M) with as n increases.
For many graph properties, this is the case. If P is any graph property which is monotone with respect to the subgraph ordering (meaning that if A is a subgraph of B and A satisfies P, then B will satisfy P as well), then the statements "P holds for almost all graphs in G(n, p)" and "P holds for almost all graphs in " are equivalent (provided tends to infinity). For example, this holds if P is the property of being connected, or if P is the property of containing a Hamiltonian cycle. However, this will not necessarily hold for non-monotone properties (e.g. the property of having an even number of edges).
In practice, the G(n, p) model is the one more commonly used today, in part due to the ease of analysis allowed by the independence of the edges.
With the notation above, a graph in G(n, p) has on average edges. The distribution of the degree of any particular vertex is binomial:[1]
where n is the total number of vertices in the graph. Since
this distribution is Poisson for large n and .
In a 1960 paper, Erdős and Rényi[2] described the behavior of G(n, p) very precisely for various values of p. Their results included that:
Thus is a sharp threshold for the connectedness of G(n, p).
Further properties of the graph can be described almost precisely as n tends to infinity. For example, there is a k(n) (approximately equal to ) such that the largest clique in G(n, 0.5) has almost surely either size k(n) or k(n) + 1.
Thus, even though finding the size of the largest clique in a graph is NP-complete, the size of the largest clique in a "typical" graph (according to this model) is very well understood.
In percolation theory one examines a finite or infinite graph and removes edges randomly. Thus the Erdős–Rényi process is in fact percolation on the complete graph. As percolation theory has much of its roots in physics, much of the research done was on the lattices in Euclidean spaces. The transition at from giant component to small component has analogs for these graphs, but for lattices the transition point is difficult to determine. Physicists often refer to study of the complete graph as a mean field theory. Thus the Erdős–Rényi process is the mean-field case of percolation.
Some significant work was also done on percolation on random graphs. From a physicist's point of view this would still be a mean-field model, so the justification of the research is often formulated in terms of the robustness of the graph, viewed as a communication network. Given a random graph of n >> 1 nodes with an average degree <k>. Remove randomly a fraction 1 − p' of nodes and leave only a fraction p' from the network. There exists a critical percolation threshold below which the network becomes fragmented while above a giant connected component of order n exists. The relative size of the giant component, , is given by[3][4][5][6]
Both of the two major assumptions of the G(n, p) model (that edges are independent and that each edge is equally likely) may be inappropriate for modeling real-life phenomena. In particular, an Erdős–Rényi graph does not have heavy tails, as is the case in many real networks. Moreover, it has low clustering, unlike many social networks. For popular modeling alternatives, see Barabási–Albert model and Watts and Strogatz model. A model for interacting ER networks was developed recently by Buldyrev et al..[7]
The G(n, p) model was first introduced by Edgar Gilbert in a 1959 paper which studied the connectivity threshold mentioned above. The G(n, M) model was introduced by Erdős and Rényi in their 1959 paper. As with Gilbert, their first investigations were as to the connectivity of G(n, M), with the more detailed analysis following in 1960.